﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace zielonka.co.uk.extensions.system.collections
{
    // Description: 
    /*
        List<int> list1 = { 3, 5, 1, 2, 9, 4, 6 };
        list1.InsertionSort((a,b) => a - b);
        //list is now in order of 1,2,3,4,5,6,9
      */

    public static partial class ListExtensions
    {
        /// <summary>
        /// Performs an insertion sort on this list.
        /// </summary>
        /// <typeparam name="T">The type of the list supplied.</typeparam>
        /// <param name="list">the list to sort.</param>
        /// <param name="comparison">the method for comparison of two elements.</param>
        /// <returns></returns>
        public static void InsertionSort<T>(this IList<T> list, Comparison<T> comparison)
        {
            for (int i = 2; i < list.Count; i++)
            {
                for (int j = i; j > 1 && comparison(list[j], list[j - 1]) < 0; j--)
                {
                    T tempItem = list[j];
                    list.RemoveAt(j);
                    list.Insert(j - 1, tempItem);
                }
            }
        }
    }
}
